package leetcode.pre50;

import offerbook.Code16_17;
import utils.ListNode;

/**
 * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
 * <p>
 * 示例：
 * <p>
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 * <p>
 * 见{@link leetcode.a_总结分布.Code12_链表问题}
 * @date 2019/11/20 0020 下午 11:22
 */


public class Code21_MergeTwoSortedLink {


    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null || l2 == null) return l1 == null ? l2 : l1;
        ListNode temp;
        if(l1.val < l2.val){
            temp = l1;
            l1.next = mergeTwoLists(l1.next,l2);
        }else {
            temp = l2;
            l2.next = mergeTwoLists(l1,l2.next);
        }
        return temp;
    }
    /**
     * 方式2：不需要额外空间复杂度。在原来链表上改变。
     * 递归版，空间复杂度是max(N,M)
     */
    public static ListNode merge2(ListNode p1,ListNode p2) {
        if (p1 == null || p2 == null) return p1 == null ? p2 : p1;
        ListNode node;
        if(p1.val < p2.val){
            node = p1;
            node.next = merge2(p1.next,p2);
        }else {
            node = p2;
            node.next = merge2(p1,p2.next);
        }
        return node;
    }

}
